import java.util.Arrays;

/**
 * @author LKQ
 * @date 2021/12/20 12:01
 * @description 注意查找长度大于某值的元素，可以先排序，后用二分查找找到该值，然后n.length-l，就是有多少个大于的元素。
 */
public class Solution {
    public static void main(String[] args) {
        Solution  solution = new Solution();
        String[] queries = {"bbb", "cc"}, words = {"a", "aa", "aaa", "aaaa"};
        int[] ans = solution.numSmallerByFrequency(queries, words);
        // 输出整型数组，用Arrays.toString.
        System.out.println(Arrays.toString(ans));
    }

    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] wordsAns = new int[words.length];
        int start = 0;
        for (String word: words) {
            wordsAns[start++] = f(word);
        }
        Arrays.sort(wordsAns);
        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int target  = f(queries[i]);
            int l = 0, r = words.length-1;
            // 此处用二分查找，如果用for时间复杂度将提高。
            while (l <= r) {
                int mid = (l + r) / 2;
                if (wordsAns[mid] > target) {
                    r = mid -1;
                }else {
                    l = mid + 1;
                }
            }
            result[i] = words.length - l;
        }
        return result;
    }

    public int f(String s) {
        char c = s.charAt(0);
        for (int i = 0; i < s.length(); i++) {
            char temp = s.charAt(i);
            if (c > temp) {
                c = temp;
            }
        }
        int length = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == c) {
                length++;
            }
        }
        return length;
    }
}
